package top.minuy.structure.graph.search.depth.dfs;

import top.minuy.structure.graph.representations.table.Graph;

import java.util.ArrayList;
import java.util.List;

/**
 * 完成对图的深度优先遍历
 *
 * @author Minuy
 * @time 11:34
 * @date 2021/11/16
 */
public class GraphDFSV1 {
    private Graph g;
    private boolean[] isVisited;

    private List<Integer> order;

    public GraphDFSV1(Graph g) {
        this.g = g;
        this.isVisited = new boolean[g.V()];

        order = new ArrayList<>();
        order(0);
    }

    private void order(int v) {
        isVisited[v] = true;

        order.add(v);

        for (Integer w : g.adj(v)) {
            if (!isVisited[w]) {
                order(w);
            }
        }
    }

    public Iterable<Integer> order() {
        return order;
    }

}
